package com.agile.leetcode.easy.topN;

import java.util.Arrays;

/**
 * @Author:ChenZhangKun
 * @Date: 2023/1/2 16:15
 */
public class Solution {
    public static void main(String[] args) {
        int[] arr={1,5,0,3,5,9,5,7,1,3,2};
        int[] leastNums = getLeastNums(arr, 4);
        System.out.println(Arrays.toString(leastNums));
    }
    public static int[] getLeastNums(int[] arr,int k){
        if (arr==null || arr.length == 0) return null;
        //
        if (k>arr.length) return arr;
        int low=0,high = arr.length - 1;
        quick(arr,low,high,k);
        return Arrays.copyOf(arr,k);
    }
    // 比较
    private static void quick(int[] arr,int low, int high, int k) {
        if (low < high){
            int pivot=partition(arr,low, high);
            if (pivot==k-1){
                return;
            }
            if (pivot>k-1){
                // high左移
                quick(arr, low, pivot-1, k);
            }else {
                // low右移
                quick(arr,pivot+1,high,k);
            }
        }
    }

    private static int partition(int[] arr, int low, int high) {
        //取arr[low]作为枢纽元素pivot
        int pivot=arr[low];
        while(low<high){
            //右边找到比pivot小的
            while(low<high&&arr[high]>=pivot){
                high--;
            }
            //交换
            arr[low]=arr[high];
            //左边找到比pivot大的
            while(low<high&&arr[low]<=pivot){
                low++;
            }
            //交换
            arr[high]=arr[low];
        }
        //枢纽元素归位
        arr[low]=pivot;
        return low;
    }
}
